1.1 Statements

This week has been all about logic, and is pretty much the foundation of most of maths! To begin, we need some ‘building blocks’, and these come in the form of statements — sentences which are either true or false. For example, ‘The sky is blue’ is a statement, whereas ‘Why is the sky blue?’ is not. In this course, statements are denoted by capital letters (usually \(P,Q,R,\ldots\))1

Now that we have some statements, it makes sense to see if we can build something more complicated using them, and this is where the idea of logical operations come in. Suppose \(P\) and \(Q\) are statements. Then, there are four main ones you should be aware of:

  • Conjunction (\(P \wedge Q\)): Said ‘\(P\) and \(Q\)’, this is true if both \(P\) and \(Q\) are true; it is false otherwise.
  • Disjunction (\(P \;\vee\; Q\)): Said ‘\(P\) or \(Q\)’, this is true when at least one of \(P\) or \(Q\) is true.
  • Negation (\(\neg P\)): Said ‘not \(P\)’, this is true when \(P\) is false, and vice versa.
  • Implication (\(P\Rightarrow Q\)): We have that ‘\(P\) implies \(Q\)’ is true, except when \(P\) is true and \(Q\) is false.2 If you’re still unsure as to what this statement means, there’s a good example here.

One way we can represent these statements is via a truth table. Below is a (combined) truth table for \(P \Rightarrow Q\) and \(\neg P \;\vee Q\):

\[\begin{equation*} \begin{array}{c|c||c|c|c} P & Q & P \Rightarrow Q & \neg P & \neg P \; \vee Q \\ \hline T & T & T & F & T \\ T & F & F & F & F \\ F & T & T & T & T \\ F & F & T & T & T \\ \end{array} \end{equation*}\]

Note that in this table, the ‘simple’ statements are on the left, and the ‘compound’ statements are written afterwards.3 Also, what we can see is that the truth table columns for both \(P \Rightarrow Q\) and \(\neg P \;\vee Q\) are identical. This means that both statements are equivalent, leading to a fifth logical operation:

  • Equivalence (\(P \Leftrightarrow Q\)): Two statements are equivalent if they’re both simultaneously true or simultaneously false. This can also be written \((P \Rightarrow Q) \wedge (Q \Rightarrow P)\).

In regards to statements, there are two more types which we can discuss. Firstly, if a statement is always true, it is known as a tautology. Similarly, if a statement is always false, it is known as a contradiction.

  1. You can use any capital letter you want; I can only presume we start at \(P\) because of the word ‘proposition’.↩︎

  2. In case it comes up in anything you read, we can also say that \(P\) is sufficient for \(Q\) and also that \(Q\) is necessary for \(P\).↩︎

  3. If you’re reading the PDF version of this, ignore this footnote. Ideally, you’d separate the simple statements (\(P\) and \(Q\)) from the compound ones by use of a double vertical line. However, due to Markdown’s apparent lack of syntax for adding a double line, you’ll just have to imagine one there.↩︎